package io.github.handyang.algorithms.sort;

public class ThreeWayQuickSortAlgorithms implements SortAlgorithms {

    @Override
    public void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int s, int e) {
        if (s >= e) return;
        int l = s, i = s + 1, r = e;

        int key = arr[l];
        while (i <= r) {
            if (arr[i] == key) i++;
            else if (arr[i] > key) swap(arr, i, r--);
            else swap(arr, l++, i++);
        }

        sort(arr, s, l - 1);
        sort(arr, r + 1, e);
    }
}
